Maximal Square

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing all 1’s and return its area.

For example, given the following matrix:

  1. 1 0 1 0 0
  2. 1 0 1 1 1
  3. 1 1 1 1 1
  4. 1 0 0 1 0

Return 4.

Solution:

  1. public class Solution {
  2.   public int maximalSquare(char[][] a) {
  3.       if (a == null || a.length == 0 || a[0].length == 0)
  4.         return 0;
  6.       int max = 0;
  7.       int n = a.length;
  8.       int m = a[0].length;
  10.       // recurrence formula:
  11.       // dp(i, j) = min{ dp(i-1, j-1), dp(i-1, j), dp(i, j-1) }
  12.       int[][] dp = new int[n + 1][m + 1];
  14.       for (int i = 1; i <= n; i++) {
  15.         for (int j = 1; j <= m; j++) {
  16.           if (a[i - 1][j - 1] == '1') {
  17.             dp[i][j] = Math.min(
  18.               dp[i - 1][j - 1], 
  19.               Math.min(dp[i - 1][j], dp[i][j - 1])
  20.             ) + 1;
  21.             max = Math.max(max, dp[i][j]);
  22.           }
  23.         }
  24.       }
  26.       // return the area
  27.       return max * max;
  28.   }
  29. }